{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Sum-Product Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hideCode": true
   },
   "source": [
    "#### The TL;DR\n",
    "\n",
    "The goal of the sum-product algorithm is to compute the marginal distribution $p(x)$ via a product of *messages*:\n",
    "\n",
    "$$\n",
    "    p(x) = \\prod_{s\\in \\text{ne}(x)} \\mu_{f_s\\to x}(x)\n",
    "$$\n",
    "\n",
    "The term $\\mu_{\\cdot\\to\\cdot}$ is called a message, and there exist two types of messages:\n",
    "1. From factor nodes to variables nodes $\\mu_{f_s\\to x}(x)$\n",
    "2. From variable nodes to factor nodes $\\mu_{x_m \\to f_s}(x_m)$\n",
    "\n",
    "To start the sum-product algorithm, we pick a leaf node\n",
    "* If the leaf node is a variable node\n",
    "$$\n",
    "    \\mu_{x\\to f}(x) = 1\n",
    "$$\n",
    "* If the leaf node is a factor node\n",
    "$$\n",
    "    \\mu_{f\\to x}(x) = f(x)\n",
    "$$\n",
    "\n",
    "We then gradually construct messages until we reach a desired node considering the following expressions for messages\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    \\mu_{f_s \\to x}(x) &= \\sum_{x_1}\\cdots\\sum_{x_M} f_s(x, x_1, \\ldots, x_M) \\prod_{m\\in\\text{ne}(f_s) \\setminus x}\\mu_{x_m\\to f_s}(x_m)\\\\\n",
    "    \\mu_{x_m \\to f_s}(x) &= \\prod_{l\\in\\text{ne}(x_m)\\setminus f_s}\\mu_{f_l\\to x_m}(x_m)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "* **Note**: the set of variables $\\{x, x_1, \\ldots, x_M\\}$ correspond to the set of variables adjacent to the factor node $f_s$. That is  \n",
    "\n",
    "$$\n",
    "    \\{x_m\\}_{m=1}^M = \\{x \\vert x \\in \\text{ne}(f_s)\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "---\n",
    "\n",
    "### Sum Product in English:\n",
    "\n",
    "1. Arbitrarly pick any node as the root\n",
    "2. Propagate messages from the leaves to the root node\n",
    "3. After propagation, the root node will have received messages from all of its neighbors, thus allowing the root to send messages to its neighbors\n",
    "4. Each neighboring node of the root will have already recieved all of the messages thus allowing it to send out messages along the links going away  frm the root and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "The joint distribution of a factor graph can be written as a product of the form\n",
    "\n",
    "$$\n",
    "    p({\\bf x}) = \\prod_{s\\in\\text{ne}({\\bf x})} F_s({\\bf x}, {\\bf X}_s)\n",
    "$$\n",
    "\n",
    "Where\n",
    "\n",
    "* $\\text{ne}(\\bf x)$ is the set of factor nodes that are neighbors of ${\\bf x}$\n",
    "* ${\\bf X}_s$ is the set of all variables (factor nodes and variable nodes) in the subtree connected to the variable node ${\\bf x}$ via the factor node $f_s$\n",
    "* $F_s({\\bf x}, {\\bf X}_s)$ is the product of all the factors in the  group associated with factor $f_s$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
